package com.cat.dataStructure03;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges/description/
 * @create 2025/11/17 16:47
 * @since JDK17
 */

public class Solution79 {
    public int countWays(int[][] ranges) {
        int n = ranges.length, m = 0, ans = 1, N = ((int) 1e9) + 7;
        Arrays.sort(ranges, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return b[1] - a[1];
            }
        });
        for (int i = 0, j = 0; i < n; m++, i = j) {
            int max = ranges[i][1];
            while (j < n && ranges[j][0] <= max) {
                max = Math.max(max, ranges[j][1]);
                j++;
            }
        }
        for (int i = 0; i < m; i++) {
            ans = ans * 2 % N;
        }

        return ans;
    }
}
